#GENERAL_MACHINE 2019.10.26
#部分递归
def zero
	0
end

def increment(n)
	n + 1
end

def two
	increment(increment(zero))
end

def three
	increment(increment(increment(zero)))
end

def recurse(f, g, *arguments)
	*others, last = arguments
	if last.zero?
		send(f, *others)
	else
		easier_last   = last - 1
		easier_arguments = others + [easier_last]
		easier_result = recurse(f, g, *easier_arguments)
		send(g, *easier_arguments, easier_result)
	end
end

def add_zero_to_x(x)
	x
end

def increment_easier_arguments(x, easier_y, easier_result)
	increment(easier_result)
end

def add(x, y)
	recurse(:add_zero_to_x, :increment_easier_arguments, x, y);
end

def multiply_zero_to_x(x)
	zero
end

def add_x_to_easier_result(x, easier_y, easier_result)
	add(x, easier_result)
end

def multiply(x, y)
	recurse(:multiply_zero_to_x, :add_x_to_easier_result, x, y)
end

def easier_x(easier_x, easier_result)
	easier_x
end

def decrement(x)
	recurse(:zero, :easier_x, x)
end

def sub_zero_to_x(x)
	x
end

def decrement_easier_arguments(x, easier_y, easier_result)
	decrement(easier_result)
end

def sub(x, y)
	recurse(:sub_zero_to_x, :decrement_easier_arguments, x, y)
end

def minimize
	n = 0
	n = n + 1 until yield(n).zero?
	n
end

def divide(x, y)
	minimize {|n| sub(increment(x), multiply(y, increment(n)))}
end

#SKI组合子
class SKIsymbol < Struct.new(:name)
	def to_s
		name.to_s
	end
	def inspect
		to_s
	end
end

class SKICall < Struct.new(:left, :right)
	def to_s 
		"#{left}[#{right}]"
	end
	def inspect
		to_s
	end
end

class SKICombinator < SKIsymbol
end

S, K, I = [:S, :K, :I].map{|name| SKICombinator.new(name)}

# puts SKIsymbol.new(:x)
# puts SKICall.new(SKIsymbol.new(:I), SKIsymbol.new(:x))

def S.call(a, b, c)
	SKICall.new(SKICall.new(a, c), SKICall.new(b, c))
end

def K.call(a, b)
	a
end

def I.call(a)
	a
end

# puts S.call(SKIsymbol.new(:x), SKIsymbol.new(:y), SKIsymbol.new(:z))

class SKIsymbol
	def combinator
		self
	end
	def arguments
		[]
	end
	def callable?(*arguments)
		false
	end
	def S.callable?(*arguments)
		arguments.length == 3
	end
	def K.callable?(*arguments)
		arguments.length == 2
	end
	def I.callable?(*arguments)
		arguments.length == 1
	end
end

class SKICall
	def combinator
		left.combinator
	end
	def arguments
		left.arguments + [right]
	end
end

class SKICombinator
	def callable?(*arguments)
		arguments.length == method(:call).arity
	end
end

# x, y, z = [:x, :y, :z].map {|name| SKIsymbol.new(name)}
# expression = SKICall.new(SKICall.new(x, y), z)
# puts expression.combinator.callable?(*expression.arguments)
# expression = SKICall.new(SKICall.new(S, x), y)
# puts expression.combinator.callable?(*expression.arguments)
# expression = SKICall.new(SKICall.new(SKICall.new(S, x), y), z)
# puts expression.combinator.callable?(*expression.arguments)

class SKIsymbol
	def reducible?
		false
	end
end


class SKICall
	def reducible?
		left.reducible? || right.reducible? || combinator.callable?(*arguments)
	end
	def reduce
		if left.reducible?
			SKICall.new(left.reduce, right)
		elsif right.reducible?
			SKICall.new(left, right.reduce)
		else
			combinator.call(*arguments)
		end
	end
end

# x, y, z = [:x, :y, :z].map {|name| SKIsymbol.new(name)}
# swap = SKICall.new(SKICall.new(S, SKICall.new(K, SKICall.new(S, I))), K)
# expression = SKICall.new(SKICall.new(swap, x), y)
# while expression.reducible?
	# puts expression
	# expression = expression.reduce
# end
# puts expression

class SKIsymbol
	def as_a_function_of(name)
		if self.name == name
			I
		else 
			SKICall.new(K, self)
		end
	end
end

class SKICombinator
	def as_a_function_of(name)
		SKICall.new(K, self)
	end
end

class SKICall
	def as_a_function_of(name)
		left_function  = left.as_a_function_of(name)
		right_function = right.as_a_function_of(name)
		
		SKICall.new(SKICall.new(S, left_function), right_function)
	end
end

# original = SKICall.new(SKICall.new(S, K), I)
# func = original.as_a_function_of(:x)
# expr = SKICall.new(func, SKIsymbol.new(:y))
# while expr.reducible?
	# puts expr
	# expr = expr.reduce
# end
# puts expr

# original = SKICall.new(SKICall.new(S, SKIsymbol.new(:x)), I)
# func = original.as_a_function_of(:x)
# expr = SKICall.new(func, SKIsymbol.new(:y))
# while expr.reducible?
	# puts expr
	# expr = expr.reduce
# end
# puts expr

#约塔

